<?php

defined('MOODLE_INTERNAL') || die();

global $CFG;
require_once($CFG->dirroot . '/question/type/preg/authoring_tools/preg_explaining_graph_misc.php');

/** 
* Take parameter from string on DOT (language).
* @param str - string on DOT.
* @param parameter – parameter, which you want to cut.
* @return - substring with parameter.
*/
function take_parameter_from_str($str, $parameter) {
    $countparameters = substr_count($str, $parameter);
    $resultsearch = false;
    $resultsubstr = '';
    $pos = 0;

    for ($i = 0; $i < $countparameters && !$resultsearch; $i++) {
        $pos = strpos($str, $parameter);
        if (($pos == 0) || ($pos > 0 && !ctype_alpha($str[(int)$pos - 1]))) {
            $resultsearch = true;
            $pos += strlen($parameter);

            while ($pos < strlen($str) && !ctype_alpha($str[$pos]) && $str[$pos] != ',') {
            $pos++;
            }

            while ($pos < strlen($str) && $str[$pos] != '"' && $str[$pos] != ',' && $str[$pos] != ';') {
                $resultsubstr .= $str[$pos];
                $pos++;
            }
        } else {
            $pos += strlen($parameter);
            $str = substr($str, $pos, strlen($str) - $pos);  
        }
    }
    
    return $resultsubstr;
}

/** 
* Extracts information about the node of the graph from string.
* @param str - string on DOT.
* @return - node of the graph.
*/
function add_node_of_graph($str) {
    $nodeofgraph = new qtype_preg_explaining_graph_tool_node(array(''), '', '', '', '', '');
    $nodeofgraph->shape = take_parameter_from_str($str, 'shape');
    $nodeofgraph->id = take_parameter_from_str($str, 'id');
    $nodeofgraph->color = take_parameter_from_str($str, 'color');
    $nodeofgraph->style = take_parameter_from_str($str, 'style');
    $nodeofgraph->fillcolor = take_parameter_from_str($str, 'fillcolor');

    if ($nodeofgraph->shape == 'record') {
        preg_match_all('/<TD>(.*?)<\/TD>/', $str, $array_temp);
        $nodeofgraph->label = $array_temp[1];

        if (preg_match('/Any character from/', $str)) {
            $nodeofgraph->invert = false;
        } else {
            $nodeofgraph->invert = true;
        }
    } else {
        $nodeofgraph->label = array(take_parameter_from_str($str, 'label'));
    }
    
    return $nodeofgraph;
}

/** 
* Analyzes subgraph on DOT-language: allocates nodes, other nested subgraphs and properties.
* @param digraph – list of strings with digraph on DOT.
* @param pos – index of beginning of the string with subgraph.
* @return - subgraph.
*/
function analysis_subgraph($digraph, &$pos) {
    $buffer = new qtype_preg_explaining_graph_tool_subgraph('', '');
    $level = 0;
    $size = count($digraph);
    $subgraphisend = false;
    static $nodesofgraph = array();
    
    // Add id and label for current subgraph
    if (substr_count($digraph[$pos], 'digraph')) {
        $buffer->id = 'explaining_graph';
    } else {
        $buffer->label = take_parameter_from_str($digraph[$pos], 'label');
        $buffer->id = take_parameter_from_str($digraph[$pos], 'id');
    }
    
    for ($i = $pos; $i < $size; $i++) {
        // If string contains '{'
        if (substr_count($digraph[$i], '{')) {
            // Depth of pass increases
            $level++;
        }

        // If string contains '}'
        if (substr_count($digraph[$i], '}')) {
            // Depth of pass decreases
            $level--;

            if ($level < 1) {
                $subgraphisend = true;
            }
        }

        // Add node for current subgraph
        if (!$subgraphisend && $level == 1 && !substr_count($digraph[$i], '->') && preg_match('"nd\d+_?\d*_?\d*"', $digraph[$i])) {
            array_push($buffer->nodes, add_node_of_graph($digraph[$i]));
            $nodesofgraph[take_parameter_from_str($digraph[$i], 'id')] = end($buffer->nodes);
        }

        // Add link for current subgraph
        if (!$subgraphisend && $level == 1 && substr_count($digraph[$i], '->')) {
            array_push($buffer->links, add_link_of_graph($digraph[$i], $nodesofgraph, $buffer));
        }
        
        // Add subgraph for current subgraph
        if (!$subgraphisend && $level == 2 && substr_count($digraph[$i], 'subgraph')) {
            array_push($buffer->subgraphs, analysis_subgraph($digraph, $i));
        }
    }

    return $buffer;
}

/** 
* Extracts information about the link of the graph between nodes from string.
* @param str - string on DOT.
* @param nodesofgraph - array of references to nodes.
* @param parentsubgraph - reference to parent subgraph.
* @return - link of the graph between nodes.
*/
function add_link_of_graph($str, $nodesofgraph, $parentsubgraph) {
    $linkofgraph = new qtype_preg_explaining_graph_tool_link('', null, null);
    preg_match_all('"nd\d+_?\d*_?\d*"', $str, $temp_array);
    $linkofgraph->source = $nodesofgraph[str_replace('nd', 'graphid_', $temp_array[0][0])];
    $linkofgraph->destination = $nodesofgraph[str_replace('nd', 'graphid_', $temp_array[0][1])];
    $linkofgraph->label = take_parameter_from_str($str, 'label');
    $linkofgraph->owner = $parentsubgraph;
    
    return $linkofgraph;
}

/** 
* Checks subgraph for membership of given subgraph.
* @param subgraph - subgraph in which carried the search.
* @param subgraphforcheck - search subgraph.
* @return - true - search subgraph is found, false - search subgraph is not found.
*/
function find_subgraph($subgraph, $subgraphforcheck) {
    if (cmp_graphs($subgraph, $subgraphforcheck)) {
        return true;
    } else {
        foreach ($subgraph->subgraphs as $iter) {
            if (cmp_graphs($iter, $subgraphforcheck)) {
                return true;
            } else {
                if (find_subgraph($iter, $subgraphforcheck)) {
                    return true;
                } else {
                    return false;
                }
            }
        }
    }   
}

/**
* Compares two nodes.
* @param n1 - first node.
* @param n2 - second node.
* @return true if two nodes of graph are equal.
*/
function cmp_nodes(&$n1, &$n2) {
    if ($n1->color != $n2->color) {
        return false;
    }

    if ($n1->label != $n2->label) {
        return false;
    }

    if ($n1->shape != $n2->shape) {
        return false;
    }

    if ($n1->id != $n2->id) {
        return false;
    }

    return true;
}

/**
* Compares two graphs (subgraphs).
* @param g1 - first graph.
* @param g2 - second graph.
* @return true if two subgraphs are equal.
*/
function cmp_graphs(&$g1, &$g2) {
    if ($g1->label != $g2->label) {
        return false;
    }

    if ($g1->style != $g2->style) {
        return false;
    }

    if (count($g1->nodes) == count($g2->nodes)) {
        for ($i = 0; $i < count($g1->nodes); ++$i) {
            $isnodesnotequal = cmp_nodes($g1->nodes[$i], $g2->nodes[$i]);

            if (!$isnodesnotequal) {
                return false;
            }
        }
    } else {
        return false;
    }

    if (count($g1->entries) == count($g2->entries)) {
        for ($i = 0; $i < count($g1->entries); ++$i) {
            $isnodesnotequal = cmp_nodes($g1->entries[$i], $g2->entries[$i]);

            if (!$isnodesnotequal) {
                return false;
            }
        }
    } else {
            return false;
    }

    if (count($g1->exits) == count($g2->exits)) {
        for ($i = 0; $i < count($g1->exits); ++$i) {
            $isnodesnotequal = !cmp_nodes($g1->exits[$i], $g2->exits[$i]);

            if ($isnodesnotequal) {
                return false;
            }
        }
    } else {
        return false;
    }

    if (count($g1->links) == count($g2->links)) {
        for ($i = 0; $i < count($g1->links); ++$i) {
            if ($g1->links[$i]->label != $g2->links[$i]->label) {
                return false;
            }

            if (!cmp_nodes($g1->links[$i]->destination, $g2->links[$i]->destination)) {
                return false;
            }

            if (!cmp_nodes($g1->links[$i]->source, $g2->links[$i]->source)) {
                    return false;
            }
        }
    } else {
        return false;
    }

    if (count($g1->subgraphs) == count($g2->subgraphs)) {
        for ($i = 0; $i < count($g1->subgraphs); ++$i) {
            if (!cmp_graphs($g1->subgraphs[$i], $g2->subgraphs[$i])) {
                return false;
            }
        }
    } else {
        return false;
    }
    
    return true;
}

/** 
* Adds consecutive subgraphs as tree nodes.
* @param topgraph - top graph (subgraph) from which to take the label.
* @param lastgraph - last graph (subgraph) from which to take the label.
* @param tree - root of the tree to which will be added the node.
* @return - absent.
*/
function add_label_as_node($topgraph, $lastgraph, $tree, $numberbranchofalter) {
    $nodesoftree = take_all_nodes_from_tree($tree);

    if ($topgraph->id != 'explaining_graph' && !array_key_exists(str_replace('graphid', 'treeid', $topgraph->id), $nodesoftree)) {
        if ($topgraph->style == 'dotted') {
            if (!preg_match('/ at least /', $topgraph->label) && !preg_match('/ any number /', $topgraph->label)) {
                $tree->operands[] = new qtype_preg_node_finite_quant;
            } else {
                $tree->operands[] = new qtype_preg_node_infinite_quant;
            }
            
            end($tree->operands)->subtype = $topgraph->label;
        } else {
            $tree->operands[] = new qtype_preg_node_subexpr($topgraph->label);
        }
        
        end($tree->operands)->subpattern = $numberbranchofalter;
        end($tree->operands)->id = str_replace('graphid', 'treeid', $topgraph->id);
    }
    
    foreach ($topgraph->subgraphs as $iter) {
        if (find_subgraph($iter, $lastgraph)) {
            if ($topgraph->id != 'explaining_graph') {  
                add_label_as_node($iter, $lastgraph, end($tree->operands), $numberbranchofalter);
            } else {
                add_label_as_node($iter, $lastgraph, $tree, $numberbranchofalter);
            }
        }
    }
}

/** 
* Determines the number of the links a node or the number of nodes pointing to the node.
* @param graphnode - node for which you want to determine the number of links.
* @param linksarray - array with links of graph (subgraph).
* @param indicator - true - links of node, false - pointing links to a node.
* @return - the number of the links.
*/
function count_links_for_node_of_graph($graphnode, $linksarray, $indicator) {
    $count = 0;

    foreach ($linksarray as $iter) {
        if (($indicator && cmp_nodes($iter->source, $graphnode)) || (!$indicator && cmp_nodes($iter->destination, $graphnode))) {
            $count++;
        }
    }

    return $count;    
}

/** 
* Determines all the nodes of the graph.
* @param graph - graph (subgraph) with nodes that you want to cut.
* @return - array with nodes.
*/
function take_all_nodes_from_graph($graph) {
    $nodesarray = array();

    foreach ($graph->nodes as $iter) {
        $nodesarray[$iter->id] = $iter;
    }

    foreach ($graph->subgraphs as $iter) {
        $nodesarray = array_merge(take_all_nodes_from_graph($iter), $nodesarray);
    }

    return $nodesarray;
}

/** 
* Determines all the nodes of the tree.
* @param tree - tree (subtree) with nodes that you want to cut.
* @return - array with nodes.
*/
function take_all_nodes_from_tree($tree) {
    $nodesarray = array();
    $nodesarray[$tree->id] = $tree;

    if (property_exists($tree, 'operands')) {
        foreach ($tree->operands as $iter) {
            $nodesarray = array_merge(take_all_nodes_from_tree($iter), $nodesarray);
        }
    }

    return $nodesarray;
}

/** 
* Determines all the links of the graph.
* @param graph - graph (subgraph) with links that you want to cut.
* @return - array with links.
*/
function take_all_links_from_graph($graph) {
    $linksarray = $graph->links;

    foreach ($graph->subgraphs as $iter) {
      $linksarray = array_merge(take_all_links_from_graph($iter), $linksarray);
    }

    return $linksarray;
}

/** 
* Adds tree node such as alternative, charset, meta, esc_b_leaf_assert, circumflex_leaf_assert, dollar_leaf_assert.
* @param graph - graph with subgraphs, nodes, links.
* @param tree – syntax tree.
* @param nodeofgraph - node in the graph that you want to convert.
* @param altersarray - array with identifiers of alternatives.
* @param typenode - node type: node_alt, leaf_charset, empty_leaf_meta, esc_b_leaf_assert, circumflex_leaf_assert, dollar_leaf_assert.
* @param $numberbranchofalter - the branch number for alternative.
* @return - absent.
*/
function add_tree_node($graph, $tree, $nodeofgraph, &$altersarray, $typenode, $numberbranchofalter) {
    $nodetreeid = str_replace('graphid', 'treeid', $nodeofgraph->id); // Determine the node ID
    $checktopgraph = $nodeofgraph->owner->id == 'explaining_graph';   // Check - a graph or subgraph
    $emptyaltersarray = empty($altersarray);                          // Check - if the array with alternatives is empty
    $nodesoftree = take_all_nodes_from_tree($tree);                   // Take all nodes from tree
    $cmpgraphs = -1;                                                  // Flag for comparison subgraphs
    
    if ($checktopgraph && $emptyaltersarray) {                        // If this is top graph and there are no alternatives
        // Add link for start node
        if ($typenode == 'node_alt') {
            $tree->operands[] = new qtype_preg_node_alt;
        }
        
        if ($typenode == 'leaf_charset') {
            $charsetnode = new qtype_preg_leaf_charset();

            if ($nodeofgraph->shape == 'record') {
                $charsetnode->subtype = '[';

                if ($nodeofgraph->invert) {
                    $charsetnode->subtype .= '^';
                }

                foreach ($nodeofgraph->label as $iter) {
                    $charsetnode->subtype .= graph_name_to_tree_name($iter);
                }

                $charsetnode->subtype .= ']';
                $tree->operands[] = $charsetnode;
            } else {
                $charsetnode->subtype = $nodeofgraph->label[0];
                $newtreenode = split_node_with_word($charsetnode);

                if ($nodeofgraph->color == 'black' && $newtreenode != null) {
                    $tree->operands[] = $newtreenode;
                } else {
                    $tree->operands[] = $charsetnode;
                }
            }
        }

        if ($typenode == 'empty_leaf_meta') {
            $tree->operands[] = new qtype_preg_leaf_meta();
        }

        if ($typenode == 'esc_b_leaf_assert') {
            if (preg_match('/not /', $nodeofgraph->label[0])) {
                $tree->operands[] = new qtype_preg_leaf_assert_esc_b(true);
            } else {
                $tree->operands[] = new qtype_preg_leaf_assert_esc_b(false);
            }
        }

        if ($typenode == 'circumflex_leaf_assert') {
            $tree->operands[] = new qtype_preg_leaf_assert_circumflex;
        }

        if ($typenode == 'dollar_leaf_assert') {
            $tree->operands[] = new qtype_preg_leaf_assert_dollar;
        }
        
        end($tree->operands)->subpattern = $numberbranchofalter;

        if ($typenode == 'esc_b_leaf_assert' || $typenode == 'circumflex_leaf_assert' || $typenode == 'dollar_leaf_assert') {
            $nodetreeid .= '_' . $numberbranchofalter;
        } elseif ($typenode == 'empty_leaf_meta') {
            $nodetreeid .= 'N';
        }

        end($tree->operands)->id = $nodetreeid;
    }
        
    if (!$emptyaltersarray) {
        $nodesofgraph = take_all_nodes_from_graph($graph);                                     // Take all nodes from graph
        $lastaltergraphid = str_replace('treeid', 'graphid', end($altersarray));               // Determine id of last alternative
        $cmpgraphs = cmp_graphs($nodesofgraph[$lastaltergraphid]->owner, $nodeofgraph->owner);
    }
    
    // If this is top graph and there are alternatives or if this is subgraph, there are alternatives and if the subgraph of last alternative is a subgraph of a graph node
    if (!$emptyaltersarray && ($checktopgraph) || (!$checktopgraph && $cmpgraphs == 1)) {
        // Add link for last alternative
        if ($typenode == 'node_alt') {
            $nodesoftree[end($altersarray)]->operands[] = new qtype_preg_node_alt;
        }
        
        if ($typenode == 'leaf_charset') {
            $charsetnode = new qtype_preg_leaf_charset();

            if ($nodeofgraph->shape == 'record') {
                $charsetnode->subtype = '[';

                if ($nodeofgraph->invert) {
                    $charsetnode->subtype .= '^';
                }

                foreach ($nodeofgraph->label as $iter) {
                    $charsetnode->subtype .= graph_name_to_tree_name($iter);
                }

                $charsetnode->subtype .= ']';
                $nodesoftree[end($altersarray)]->operands[] = $charsetnode;
            } else {
                $charsetnode->subtype = $nodeofgraph->label[0];
                $newtreenode = split_node_with_word($charsetnode);

                if ($nodeofgraph->color == 'black' && $newtreenode != null) {
                    $nodesoftree[end($altersarray)]->operands[] = $newtreenode;
                } else {
                    $nodesoftree[end($altersarray)]->operands[] = $charsetnode;
                }
            }
        }

        if ($typenode == 'empty_leaf_meta') {
            $nodesoftree[end($altersarray)]->operands[] = new qtype_preg_leaf_meta();
        }

        if ($typenode == 'esc_b_leaf_assert') {
            if (preg_match('/not /', $nodeofgraph->label[0])) {
                $nodesoftree[end($altersarray)]->operands[] = new qtype_preg_leaf_assert_esc_b(true);
            } else {
                $nodesoftree[end($altersarray)]->operands[] = new qtype_preg_leaf_assert_esc_b(false);
            }
        }

        if ($typenode == 'circumflex_leaf_assert') {
            $nodesoftree[end($altersarray)]->operands[] = new qtype_preg_leaf_assert_circumflex;
        }

        if ($typenode == 'dollar_leaf_assert') {
            $nodesoftree[end($altersarray)]->operands[] = new qtype_preg_leaf_assert_dollar;
        }
        
        end($nodesoftree[end($altersarray)]->operands)->subpattern = $numberbranchofalter;

        if ($typenode == 'esc_b_leaf_assert' || $typenode == 'circumflex_leaf_assert' || $typenode == 'dollar_leaf_assert') {
            $nodetreeid .= '_' . $numberbranchofalter;
        } elseif ($typenode == 'empty_leaf_meta') {
            $nodetreeid .= 'N';
        }

        end($nodesoftree[end($altersarray)]->operands)->id = $nodetreeid;
    }
    
    // If this is top graph and there are no alternatives or if this is subgraph, there are alternatives and if the subgraph of last alternative is not a subgraph of a graph node
    if (!$checktopgraph && (($emptyaltersarray) || (!$emptyaltersarray && $cmpgraphs == 0))) {
        $subgraphnodeid = str_replace('graphid', 'treeid', $nodeofgraph->owner->id);           // Determine ID of parent subgraph
        
        // Add link for subgraph
        if ($typenode == 'node_alt') {
            $nodesoftree[$subgraphnodeid]->operands[] = new qtype_preg_node_alt;
        }
        
        if ($typenode == 'leaf_charset') {
            $charsetnode = new qtype_preg_leaf_charset();

            if ($nodeofgraph->shape == 'record') {
                $charsetnode->subtype = '[';

                if ($nodeofgraph->invert) {
                    $charsetnode->subtype .= '^';
                }

                foreach ($nodeofgraph->label as $iter) {
                    $charsetnode->subtype .= graph_name_to_tree_name($iter);
                }

                $charsetnode->subtype .= ']';
                $nodesoftree[$subgraphnodeid]->operands[] = $charsetnode;
            } else {
                $charsetnode->subtype = $nodeofgraph->label[0];
                $newtreenode = split_node_with_word($charsetnode);

                if ($nodeofgraph->color == 'black' && $newtreenode != null) {
                    $nodesoftree[$subgraphnodeid]->operands[] = $newtreenode;
                } else {
                    $nodesoftree[$subgraphnodeid]->operands[] = $charsetnode;
                }
            }
        }

        if ($typenode == 'empty_leaf_meta') {
            $nodesoftree[$subgraphnodeid]->operands[] = new qtype_preg_leaf_meta();
        }

        if ($typenode == 'circumflex_leaf_assert') {
            $nodesoftree[$subgraphnodeid]->operands[] = new qtype_preg_leaf_assert_circumflex;
        }

        if ($typenode == 'dollar_leaf_assert') {
            $nodesoftree[$subgraphnodeid]->operands[] = new qtype_preg_leaf_assert_dollar;
        }

        if ($typenode == 'esc_b_leaf_assert') {
            if (preg_match('/not /', $nodeofgraph->label[0])) {
                $nodesoftree[$subgraphnodeid]->operands[] = new qtype_preg_leaf_assert_esc_b(true);
            } else {
                $nodesoftree[$subgraphnodeid]->operands[] = new qtype_preg_leaf_assert_esc_b(false);
            }
        }
        
        end($nodesoftree[$subgraphnodeid]->operands)->subpattern = $numberbranchofalter;

        if($typenode == 'esc_b_leaf_assert' || $typenode == 'circumflex_leaf_assert' || $typenode == 'dollar_leaf_assert') {
            $nodetreeid .= '_' . $numberbranchofalter;
        } elseif ($typenode == 'empty_leaf_meta') {
            $nodetreeid .= 'N';
        }

        end($nodesoftree[$subgraphnodeid]->operands)->id = $nodetreeid;

    }
    
    // Add identifier in array with identifiers of alternatives
    if ($typenode == 'node_alt') {
        $altersarray[] = $nodetreeid;
    }
}

/** 
* Analyzes node of graph, adds nodes of tree, adds links.
* @param nodeofgraph - node in the graph that you want to convert.
* @param graph - graph with subgraphs, nodes, links.
* @param tree – syntax tree.
* @param $numberbranchofalter - the branch number for alternative.
* @return - 0 - end of analysis, -1 - end of alternative branch.
*/
function analysis_node_of_graph($nodeofgraph, $graph, &$tree, &$numberbranchofalter)
{
    static $arraylinks;                 // Array with links of graph
    static $nodesoftree;                // Array with nodes of tree
    static $altersarray;                // Array with alternatives
    static $countlinksofalter = 0;      // Count links of alternatives
    
    // Add start node
    if ($nodeofgraph->label[0] == 'begin' && $nodeofgraph->color == 'purple' && $nodeofgraph->shape == 'box') {
        $tree = new qtype_preg_node_concat;
        $tree->id = str_replace('graphid', 'treeid', $nodeofgraph->id); 
        $tree->subpattern = $numberbranchofalter;
        $arraylinks = take_all_links_from_graph($graph);                     // Determine links of graph
    }
    
    // Add alternative
    if ($nodeofgraph->shape == 'point' && count_links_for_node_of_graph($nodeofgraph, $arraylinks, true) > 1) {
        add_tree_node($graph, $tree, $nodeofgraph, $altersarray, qtype_preg_node::TYPE_NODE_ALT, $numberbranchofalter);
        $countlinksofalter += count_links_for_node_of_graph($nodeofgraph, $arraylinks, true);
    }
    
    // Find end of alternative
    if ($nodeofgraph->shape == 'point' && count_links_for_node_of_graph($nodeofgraph, $arraylinks, false) > 1 && $countlinksofalter != $numberbranchofalter) {
        $numberbranchofalter++;
        return -1;
    }
    
    // Add node - charset
    if ((($nodeofgraph->color == 'hotpink' || $nodeofgraph->color == 'black') && $nodeofgraph->shape == 'ellipse') || ($nodeofgraph->shape == 'record')) {
        add_tree_node($graph, $tree, $nodeofgraph, $altersarray, qtype_preg_node::TYPE_LEAF_CHARSET, $numberbranchofalter);
    }
    
    foreach ($arraylinks as $iter) {
        if ($iter->source->id == $nodeofgraph->id) {
            // Add esc_b_leaf_assert 
            if (preg_match('/a word boundary/', $iter->label)) {
                add_tree_node($graph, $tree, $nodeofgraph, $altersarray, qtype_preg_leaf_assert::SUBTYPE_ESC_B, $numberbranchofalter);
            }

            if (preg_match('/start of the string/', $iter->label)) {
                add_tree_node($graph, $tree, $nodeofgraph, $altersarray, qtype_preg_leaf_assert::SUBTYPE_CIRCUMFLEX, $numberbranchofalter);
            }

            if (preg_match('/end of the string/', $iter->label)) {
                add_tree_node($graph, $tree, $nodeofgraph, $altersarray, qtype_preg_leaf_assert::SUBTYPE_DOLLAR, $numberbranchofalter);
            }

            // Add subgraphs as tree nodes...
            if($nodeofgraph->owner->id != $iter->destination->owner->id) {
                $subgraphnodeid = str_replace('graphid', 'treeid', $iter->destination->owner->id);
                $nodesoftree = take_all_nodes_from_tree($tree);

                if (($subgraphnodeid != 'explaining_graph' && !array_key_exists($subgraphnodeid, $nodesoftree)) || ($subgraphnodeid == 'explaining_graph')) {
                    if (empty($altersarray)) {
                        // ... for start node
                        add_label_as_node($nodeofgraph->owner, $iter->destination->owner, $tree, $numberbranchofalter);
                    }  else {
                        $nodesofgraph = take_all_nodes_from_graph($graph);
                        $graphidalterparentsubgraph = $nodesofgraph[str_replace('treeid', 'graphid', end($altersarray))]->owner->id;

                        if ($nodeofgraph->owner->id != $graphidalterparentsubgraph && find_subgraph($nodeofgraph->owner, $iter->destination->owner)) {
                            // ... for parent subgraph
                            add_label_as_node($nodeofgraph->owner, $iter->destination->owner, $nodesoftree[str_replace('graphid', 'treeid',$nodeofgraph->owner->id)], $numberbranchofalter);
                        } else {
                            // ... for last alternative
                            add_label_as_node($nodeofgraph->owner, $iter->destination->owner, $nodesoftree[end($altersarray)], $numberbranchofalter);
                        }
                    }

                }
            }
            
            // Add nothing
            if ($nodeofgraph->shape == 'point' && count_links_for_node_of_graph($nodeofgraph, $arraylinks, true) > 1 && $iter->destination->shape == 'point' && count_links_for_node_of_graph($iter->destination, $arraylinks, false) > 1) {
                add_tree_node($graph, $tree, $nodeofgraph, $altersarray, qtype_preg_leaf_meta::SUBTYPE_EMPTY, $numberbranchofalter);
            }
            
            // Analize node - destination
            analysis_node_of_graph($iter->destination, $graph, $tree, $numberbranchofalter);

        }
    }
    
    // Delete alternative from array with alternatives
    if ($nodeofgraph->shape == 'point' && count_links_for_node_of_graph($nodeofgraph, $arraylinks, true) > 1) {
        array_pop($altersarray);
    }
    
    return 0;
}

/** 
* Adds concatenation for alternatives and ntree nodes-subgraphs.
* @param nodeoftree - alternative or tree node-subgraph.
* @param $numberbranchofalter - the branch number for alternative.
* @return - null or array with operands.
*/
function add_concatenation_for_node($nodeoftree, $numberbranchofalter) {
    $branchnumber = 0;
    $countnodes = 0;                // Number of operands for concatenation
    $arraynodes = array();
    $operandsoftreenode = array();
    $newoperand = null;

    // Add concatenations for alternative
    if ($nodeoftree->type == qtype_preg_node::TYPE_NODE_ALT) {
        while ($branchnumber <= $numberbranchofalter) {
            foreach ($nodeoftree->operands as $iter) {
                if ($iter->subpattern == $branchnumber) {
                    $countnodes++;
                    $arraynodes[] = $iter;
                }
            }

            if ($countnodes > 1) {
                $newoperand = new qtype_preg_node_concat;
                $newoperand->operands = $arraynodes;
                $operandsoftreenode[] = $newoperand;
            }

            if ($countnodes == 1) {
                $newoperand = $arraynodes[0];
                $operandsoftreenode[] = $newoperand;
            }

            $branchnumber++;
            $countnodes = 0;
            $arraynodes = array();
        }
    }

    // Add concatenation for tree node-subgraph
    if ($nodeoftree->type == qtype_preg_node::TYPE_NODE_INFINITE_QUANT || $nodeoftree->type == qtype_preg_node::TYPE_NODE_FINITE_QUANT || $nodeoftree->type == qtype_preg_node::TYPE_NODE_SUBEXPR) {
        if (count($nodeoftree->operands) > 1) {
            $newoperand = new qtype_preg_node_concat;
            $newoperand->id = $nodeoftree->id . '_0';
            $newoperand->operands = $nodeoftree->operands;
            $operandsoftreenode[] = $newoperand;
        }
    }

    return $operandsoftreenode;
}

/** 
* Splits tree node with word on subnodes.
* @param splitnode - node that you want to split.
* @return - node with operands (symbols) or null.
*/
function split_node_with_word($splitnode) {
    $size = strlen($splitnode->subtype);
    $newtreenode = null;

    if ($size > 1) {
        $newtreenode = new qtype_preg_node_concat;
        $newtreenode->id = $splitnode->id;
        $newtreenode->subpattern = $splitnode->subpattern;

        for ($i = 0; $i < $size; $i++) {
            $newtreenode->operands[] = new qtype_preg_leaf_charset;
            end($newtreenode->operands)->subtype = $splitnode->subtype[$i];
            end($newtreenode->operands)->id = $splitnode->id . '_' . $i;
            end($newtreenode->operands)->subpattern = $splitnode->subpattern;
        }
    }

    return $newtreenode;
}

/** 
* Converts name of node from graph to tree.
* @param nameofgraphnode - name of graph node.
* @return - name of tree node.
*/
function graph_name_to_tree_name($nameofgraphnode) {
    if (preg_match('/any number of times/', $nameofgraphnode)) {
        if (preg_match('/ or missing/', $nameofgraphnode)) {
            return '*';
        } else {
            return '+';
        }
    }

    if (preg_match('/may be missing/', $nameofgraphnode)) {
        return '?';
    }

    if (preg_match('/repeated/', $nameofgraphnode)) {
        if (preg_match('/from \d+ to \d+ times/', $nameofgraphnode)) {
            preg_match_all('/\d+/', $nameofgraphnode, $temp_array);
            return '{' . $temp_array[0][0] . ',' . $temp_array[0][1] . '}';
        } elseif (preg_match('/at least \d+ times/', $nameofgraphnode)) {
            preg_match_all('/\d+/', $nameofgraphnode, $temp_array);
            return '{' . $temp_array[0][0] . ',' . '}';
        } else {
            preg_match_all('/\d+/', $nameofgraphnode, $temp_array);
            return '{' . $temp_array[0][0] . '}';
        }
    }

    if (preg_match('/subpattern/', $nameofgraphnode)) {
        preg_match_all('/\d+/', $nameofgraphnode, $temp_array);
        return '(...)#' . $temp_array[0][0];
    }

    if (preg_match('/node_alt/', $nameofgraphnode)) {
        return '|';
    }

    if (preg_match('/not a decimal digit/', $nameofgraphnode)) {
        return '\\D';
    }

    if (preg_match('/a decimal digit/', $nameofgraphnode)) {
        return '\\d';
    }

    if (preg_match('/not a word character/', $nameofgraphnode)) {
        return '\\W';
    }

    if (preg_match('/a word character/', $nameofgraphnode)) {
        return '\\w';
    }

    if (preg_match('/not a white space/', $nameofgraphnode)) {
        return '\\S';
    }

    if (preg_match('/a white space/', $nameofgraphnode)) {
        return '\\s';
    }

    if (preg_match('/any character/', $nameofgraphnode)) {
        return '.';
    }

    if (preg_match('/line feed/', $nameofgraphnode)) {
        return '\\n';
    }

    if (preg_match('/carriage return character/', $nameofgraphnode)) {
        return '\\r';
    }

    if (preg_match('/tabulation/', $nameofgraphnode)) {
        return '\\t';
    }

    if (preg_match('/a vertical white space character/', $nameofgraphnode)) {
        return '\\v';
    }

    if (preg_match('/null character/', $nameofgraphnode)) {
        return '\\0';
    }

    if (preg_match('/from [\d|\w]+ to [\d|\w]+/', $nameofgraphnode)) {
        preg_match_all('/\d+|\w+/', $nameofgraphnode, $temp_array);
        return $temp_array[0][1] . '-' . $temp_array[0][3];
    }

    return $nameofgraphnode;
}

/** 
* Prints tree.
* @param $tree - syntax tree.
* @return - absent.
*/
function print_tree($tree) {
    if (!empty($tree->operands)) {
        foreach ($tree->operands as $iter) {
            $str = '[' . $tree->id . ']' . ' ' . $tree->type . ' ' . $tree->subtype . '->' . '[' . $iter->id . ']' . ' ' . $iter->type . ' ' . $iter->subtype;
            print("\n");
            print($str);
        }

        foreach ($tree->operands as $iter) {
            print_tree($iter);
        }
    }
}

/** 
* Creates tree from graph with nodes, subgraphs, links.
* @param graph - graph with subgraphs, nodes, links.
* @return - syntax tree.
*/
function create_tree($graph) {
    $graph->id = 'explaining_graph';
    $tree = null;
    $isFind = false;
    $numberbranchofalter = 0;           // The branch number for alternative

    add_id_for_graph_nodes($graph, $startid);

    // Find node-'begin'
    for ($i = 0; $i < count($graph->nodes) && !$isFind; $i++) {
        if ($graph->nodes[$i]->label[0] == 'begin' && $graph->nodes[$i]->color == 'purple' && $graph->nodes[$i]->shape == 'box') {
            $isFind = true;
            
            // Analyze node-'begin'
            analysis_node_of_graph($graph->nodes[$i], $graph, $tree, $numberbranchofalter);
        }
    }

    // Delete start node
    if (count($tree->operands) == 1) {
        $tree = $tree->operands[0];
    }

    // Take all nodes from tree
    $nodesoftree = take_all_nodes_from_tree($tree);

    // Add concatenation for alternatives, quantifiers, subexpressions
    foreach ($nodesoftree as $nodeoftree) {
        if (!empty($nodeoftree->operands)) {
            $resultoperands = add_concatenation_for_node($nodeoftree, $numberbranchofalter);

            if ($resultoperands != null) {
                $nodeoftree->operands = $resultoperands; 
            }
        }
    }

    // Take all nodes from tree
    $nodesoftree = take_all_nodes_from_tree($tree);

    // Convert names of nodes from graph to tree
    foreach ($nodesoftree as $nodeoftree) {
        $nodeoftree->subtype = graph_name_to_tree_name($nodeoftree->subtype);
    }

    return $tree;
}

/** 
* Adds id for subgraph and nodes.
* @param graph - graph with subgraphs, nodes, links.
* @param startid - starting identifier.
* @return - absent.
*/
function add_id_for_graph_nodes(&$graph, &$startid) {
    for ($i = 0; $i < count($graph->nodes); $i++) {
        $graph->nodes[$i]->id = 'graphid' . '_' . $i . '_' . $startid;
        $startid++;
    }

    for ($i = 0; $i < count($graph->subgraphs); $i++) {
        add_id_for_graph_nodes($graph->subgraphs[$i], $startid);
        $graph->subgraphs[$i]->id = 'graphid' . '_' . $i . '_' . $startid;
        $startid++;
    }
}